<html>
<head>
<TITLE>CSE5317/4305 Project #5</TITLE>
</head>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000">
<center>
<H1>CSE5317/4305 Project #5 (Simple IRs)</H1>
Due Monday April 7 at 11:59pm<p>
Worth 18% of your project grade
</center>
<p>
<hr>
<p>
For this project, you need to generate 
Intermediate Representation (IR) data structures for <b>some</b> of the ASTs.
You should not generate any MIPS code for this project.
You should generate IR data for all types of ASTs, <b>except</b> the following AST nodes:
<p>
ProcDec, RecordExp, RecordInit, RecordDeref, ArrayDeref, CallExp, CallSt, RetSt
<p>
That is, in this project, you should <b>not</b> generate IR code for
record construction, array indexing, record projection,
function/procedure call, and function/procedure prologue/epilogue (but
you should generate IR code for their bodies and store their
parameters in the symbol table).  Everything left out will be
generated by the next project.
I have also given the IR for ArrayExp AST because it's difficult.
You will have to use the TypeCheck code for ProcDec to make sure
that parameters and local variables are inserted in the Symbol table.
<p>
Your ASTs that represent IRs, when printed by <tt>toString()</tt>, should follow the following syntax:
<pre>
IRexp -> Const(INTEGER_LITERAL)         # integer constant
         Const(STRING_LITERAL)          # string constant
         Const(REAL_LITERAL)            # real constant
         Mem(IRexp)                     # retrieve the memory content at given address
         Reg(ID)                        # a register
         Binop(binop,IRexp,IRexp)       # binary operation
         Unop(unop,IRexp)               # unary operation
         Call(ID,IRexp,IRexp,...,IRexp) # set register ra to the return address,
                                        #    set v0 to the callee's static link (first IRexp),
                                        #    call function ID with the given arguments
					#    and return back the result
	 ESeq(IRStmt,IRexp)             # evaluate the statement and return the exp value
         Assert(IRexp,IRexp)            # if the first exp is true return the second exp value,
                                        #    otherwise, raise an exception
         Allocate(IRexp)		# allocate a number of words in the heap and return the address

IRstmt -> Move(Mem(IRexp),IRexp)        # set memory with given address
          Move(Reg(ID),IRexp)           # set register value
          Label(ID)                     # define a label to be the current address
          Jump(ID)                      # jump to label ID
          CJump(IRexp,ID)               # jump to label ID if condition (IRexp) is true
          Seq(IRstmt,... IRstmt)        # sequence of statements
          Call(ID,IRexp,IRexp,...,IRexp)# set register ra to the return address,
                                        #    set v0 to the callee's static link,
                                        #    and call procedure ID with the given arguments
          SystemCall(ID,IRexp)		# a system call can be: READ_INT, READ_FLOAT,
	                                #    WRITE_INT, WRITE_FLOAT, WRITE_BOOL, or WRITE_STRING
          Return()                      # jump to the address in register ra
binop -> GT | LT | EQ | GE | LE | NE | PLUS | MINUS | TIMES | SLASH | DIV | MOD | AND | OR 
unop  -> UMINUS | NOT
</pre>
<font size=3>
Read <a href="http://lambda.uta.edu/cse5317/notes/node35.html">Section 8</a> in the notes for explanation of some of them.
Note that <tt>SEQ(s1,s2)</tt> in the notes is now <tt>Seq(s1,s2,...sn)</tt>, which makes the code generation easier.
The IR <tt>Call(f,sl,e1,...,en)</tt> takes the function/procedure name, <tt>f</tt>, the static link of the callee, <tt>sl</tt>,
and zero or more arguments <tt>e1 ... en</tt>.
It pushes the arguments <tt>e1 ... en</tt> in the stack, sets the register <tt>v0</tt> to <tt>sl</tt>, calls procedure <tt>f</tt>,
and, after <tt>f</tt> returns, it pops <tt>n</tt> values from the stack.
If it is a function, it returns a value.
For this project phase, you can use the following
six reserved registers (which should not be used for any other purpose):
<pre>
fp       frame pointer
sp       stack pointer
gp       pointer to heap (implicitly used by Allocate only)
ra       return address
v0       used in passing the static link from the caller to the callee
a0       used in passing the result of a function from the callee to the caller
</pre>
For example, the IR <tt>Reg(fp)</tt> represents the register fp.
The IR code <tt>Allocate(n)</tt> allocates <tt>n</tt> words in the heap,
and returns the address of the first word, that is, it is equivalent to
<tt>gp:=gp+n*4; return gp</tt>.
You will never deallocate objects from heap.
<p>
The only thing that you have to do for this project is to write more
code in the static method <tt>code</tt> in the file <a href="pcat/Code.gen">Code.gen</a>,
which gets an AST exp (for expressions, statements, declarations, etc) as input and generates its IR.
The IR code generated is normalized by the <tt>normalize</tt> method (ie, Seq and ESeq are removed),
and the resulting list of IRs is pretty-printed in the output.
<p>
Assumptions:<br>
Every data value occupies 4 bytes regardless of its type.
More specifically, this is how you map PCAT types to IRs:
<ul>
<li> Integers and floats occupy 1 word=4 bytes.
<li> A boolean value is represented by an integer (4 bytes) and is false
  if the integer is equal to 0, true otherwise. 
<li> PCAT supports constant (immutable) strings only, which are stored in the static section
as null-terminated strings.
<li> An array is implemented as a pointer to an object in the
heap that contains the array length (1 word) followed by the array content (total number
of words in the heap is length+1).
Arrays are zero-based
(i.e. the first element of an array A of n elements is A[0] and the
last one is A[n-1]). Your generated IR code should check for out-of-bounds errors at run time (using an Assert IR).
<li> Records are also implemented as pointers to heap objects. The
pointer can be NIL (ie, equal to 0). If a record has n attributes, then the heap object will
occupy n consecutive integers (n*4 bytes), since every attribute needs
4 bytes). Accessing record attributes (e.g. in A.X, where A is a
record and X is an attribute of A) is similar to that for a
vector (the only difference is that you do not store the size of a
record).
When accessing record components, your generated IR code should check for null records at run time (using an Assert IR).
</ul>
<p>
All PCAT variables should be allocated in the run-time stack, including all global
variables (you store global variables in the activation record of the
main program).
<p>
You should generate IRs for each type of expression, declaration, etc.,
so that for each input file, you get only one IR tree (like you get one AST only).
Statements are a bit tricky. For example, the while loop:
<pre>
while c do x:= x+5;
</pre>
where <tt>x</tt> is an integer with offset -60 and <tt>c</tt> is a boolean with offset -12,
generates the following IR when printed:
<pre>
Seq(Label(loop_10_),
    CJump(Binop(EQ,Mem(Binop(PLUS,Reg(fp),Const(-12))),Const(0)),exit_11_),
    Move(Mem(Binop(PLUS,Reg(fp),Const(-60))),
         Binop(PLUS,Mem(Binop(PLUS,Reg(fp),Const(-60))),Const(5))),
    Jump(loop_10_),
    Label(exit_11_))
</pre>
Here I used the name generator <tt>new_name</tt> for labels that
generates new names, such as <tt>loop_10_</tt> and <tt>exit_11_</tt>, each time.)
<p>
PCAT read/write statements need special attention. You need to use various
system calls: READ_INT, WRITE_INT, WRITE_STRING, etc.
For example, the PCAT statement <tt>write("x = ",x)</tt> has IR:
<pre>
Seq(SystemCall(WRITE_STRING,Const("x = ")),    # write "x = "
    SystemCall(WRITE_INT,Mem(...)),            # write x
    SystemCall(WRITE_STRING,Const("\n")))      # write end=of-line
</pre>
<p>
Hints:
<ul>
<li> You need to recreate the Symbol Table used in project #4. You may also have to call typecheck
     occasionally to get the type of an AST.
<li> You need to find the correct (level,offset)
   of each variable. When you find a variable declaration, you put the entry
   <tt>VarDec(type,level,offset)</tt> in the symbol table. The method
   <tt>allocate_variable</tt> will do that for you.
<li> For a function/procedure declaration, you store
    <tt>ProcDec(type,label,level,min_offset,param1,..,paramn)</tt>,
    where type is the output type (<tt>NoType()</tt> for procedures) and a <tt>param</tt> is a formal parameter, which,
    when printed, looks like <tt>Param(ID,type)</tt>,that is, each formal parameter has a name and a type.
    The label is a globaly unique label generated by new_name(fname), where fname is the function/procedure name
    (since we can have the same function name in different scopes). Finally, level is the function level (0 for main),
    and min_offset is the next available offset in the function's frame.
<li> To handle the ExitSt(), use the LabelStack to push/pop the exit labels of loops.
    ExitSt jumps to the exit label at the top of the stack.
</ul>
<p>
You need to run your parser against all <tt>tests/*.pcat</tt> files.
For example:
<pre>
run 5 hello
</pre>
You also need to compare your output with that of the solution:
<pre>
solution 5 hello
</pre>
<p>
After ensuring that your program compiles and executes correctly,
cleanup your <tt>pcat</tt> directory using
<tt>
clean
</tt>
Then, if you are using Linux, archive your file using <tt>tar cvf pcat.tar pcat</tt>.
If you are using Windows, zip the whole directory into the file <tt>pcat.zip</tt>.
Then submit your file (<tt>pcat.tar</tt> or <tt>pcat.zip</tt>) here:
<p>
<form enctype="multipart/form-data" action="/cgi-bin/php/handin.php" method="POST">
    <input type="hidden" name="MAX_FILE_SIZE" value="10000000" />
    <input type="hidden" name="class" value="cse5317" />
    <input type="hidden" name="assignment" value="proj5" />
Submit this file: <input name="userfile" type="file" size="50"/><br/>
    <input type="submit" value="Send File" />
</form>
<p>

<hr>
<P>
<ADDRESS>Last modified: 01/08/07 by <A HREF="http://lambda.uta.edu/">Leonidas Fegaras</A></ADDRESS>
